#include<stdio.h>
#include<stdlib.h>

double f1(int n,double x)
{
	if(n==0) 
		return 1;
	else if(n==1) 
		return 2*x;
	else
	{
		return (2*x*f1(n-1,x)-2*(n-1)*f1(n-2,x));
	}
}
/*
	下面介绍如何用栈来求该多项式的值，
	这里利用了栈后进先出的特性将n 由大到小入栈，再由小到大出栈，
	每次出栈时求出该数所对应的多项式的值
	为求下一个出栈的数所对应的多项式的值做基础。

*/
double f2(int n,double x)
{
	struct STACK
	{
		int num;			//存放n的值
		double data;		//data 存放不同n对应的不同结果
	}sq[100];
	int i,top=-1;
	double sum1=1,sum2=2*x; //n=0,sum1=1;n=1,sum2=2*x
	//将n由大到小入栈 n-2 例如：当 n为4 i:4 3 2 ,top：0 1 2
	for(i=n;i>=2;i--)
	{
		top++;
		sq[top].num=i;// n n-1 ... 2
	}
	while(top>=0)
	{
		sq[top].data=(2*x*sum2-2*(sq[top].num-1)*sum1);//求出栈顶元素值
		sum1=sum2;		//sum2赋给sum1
		sum2=sq[top].data;	//将刚计算出的函数值赋值给sum2
		top--;		//指针下移
	}
	return sum2;
}


int main()
{
	int n,x;
	printf("请输入n:\n");
	scanf("%d",&n);
	printf("请输入x:\n");
	scanf("%d",&x);
	printf("用递归算法得出的函数值是:");
	double sum1=f1(n,x);
	printf("%lf\n",sum1);
	printf("用栈算法得出的函数值是:");
	double sum2=f2(n,x);
	printf("%lf\n",sum2);
	return 0;
}

